//题目:
// 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

// 示例 1：
// 输入：nums = [1,5,11,5]
// 输出：true
// 解释：数组可以分割成 [1, 5, 5] 和 [11] 。

// 示例 2：
// 输入：nums = [1,2,3,5]
// 输出：false
// 解释：数组不能分割成两个元素和相等的子集。
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    bool canPartition(vector<int>& nums) 
    {
        //题意转换：从nums中选择一些数出来，使其和等于 sum/2
        int sum=0;
        for(auto x:nums) sum+=x;
        if(sum%2==1) return false;

        int goal=sum/2;
        //判断能否从 nums 中挑选出一个子序列，使其和等于 goal
        // //1.创建dp表————dp[i][j]表示：选到第i个元素时，元素和为j的情况是否存在
        // int n=nums.size(),m=10000;
        // vector<vector<bool>> dp(n+1,vector<bool>(m+1));
        // //2.初始化
        // dp[0][0]=true;
        // for(int i=1;i<=n;i++) dp[i][0]=true;
        // //3.填表
        // for(int i=1;i<=n;i++)
        //     for(int j=1;j<=m;j++)
        //         if((j-nums[i-1]>=0 && dp[i-1][j-nums[i-1]]==true) || dp[i-1][j]==true)
        //             dp[i][j]=true;
        // //4.确定返回值
        // return dp[n][goal];

        //空间优化
        //1.创建dp表————dp[i][j]表示：选到第i个元素时，元素和为j的情况是否存在
        int n=nums.size(),m=10000;
        vector<bool> dp(m+1);
        //2.初始化
        dp[0]=true;
        //3.填表
        for(int i=1;i<=n;i++)
            for(int j=m;j>=nums[i-1];j--)
                if(dp[j-nums[i-1]]==true || dp[j]==true)
                    dp[j]=true;
        //4.确定返回值
        return dp[goal];
    }
};